import collections
import functools
from copy import copy
from typing import List


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        req_skills_set = set(req_skills)

        # 整理不需要的技能
        clear_people = []
        for person_skill in people:
            count = collections.Counter()
            for ch in person_skill:
                if ch in req_skills_set:
                    count[ch] += 1
            clear_people.append(count)

        size1 = len(clear_people)
        size2 = len(req_skills)

        @functools.lru_cache(None)
        def dfs(stat1):
            if stat1 == 0:
                return []

            # 找到还存在的最后一个技能
            idx = size2 - (stat1 & (-stat1)).bit_length()  # lowbit
            aim = req_skills[idx]

            # print("DFS状态:", bin(stat1)[2:], "->", aim, [idx])

            # 遍历寻找最优解
            ans = [i for i in range(size1)]
            for i in range(size1):
                if aim in clear_people[i]:
                    # 计算使用当前词后的新状态
                    stat2 = stat1
                    count2 = copy(clear_people[i])
                    for j in range(size2):
                        # print(j, target[-j - 1], stat2 & (1 << j), count2[target[-j - 1]])
                        if stat2 & (1 << j) and count2[req_skills[-j - 1]] > 0:
                            count2[req_skills[-j - 1]] -= 1
                            stat2 ^= (1 << j)

                    # print("DFS", bin(stat1)[2:], "->", bin(stat2)[2:], clear_stickers[i])

                    # 递归求值
                    ans = min(ans, [i] + dfs(stat2), key=lambda x: len(x))

            return ans

        return dfs((1 << size2) - 1)


if __name__ == "__main__":
    # [0,2]
    print(Solution().smallestSufficientTeam(req_skills=["java", "nodejs", "reactjs"],
                                            people=[["java"], ["nodejs"], ["nodejs", "reactjs"]]))

    # [1,2]
    print(Solution().smallestSufficientTeam(req_skills=["algorithms", "math", "java", "reactjs", "csharp", "aws"],
                                            people=[["algorithms", "math", "java"], ["algorithms", "math", "reactjs"],
                                                    ["java", "csharp", "aws"], ["reactjs", "csharp"],
                                                    ["csharp", "math"], ["aws", "java"]]))
